﻿//#define _CRT_SECURE_NO_WARNINGS
//#include <stdio.h>
//#include <string.h>
//#include <stdlib.h>
//#include <ctype.h>
// C/C++ 学习网站：https://legacy.cplusplus.com 注意旧版本（搜索）和新版本

#include "common.h"

static void print_boomerang(int n)
{ // 打印回旋镖
    if (n == 0)
        return;
    n = n > 0 ? n : -n; // 取绝对值
    printf("回旋镖图案如下：\n");
    int i, j, k;
    /*for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= 2 * n; ++j)
            if (j <= 2 * (n + 1 - i))
                printf(" ");
        for (k = 1; k <= i; ++k)
            printf("*");
        printf("\n\n");
    }
    for (i = 0; i <= n; ++i)
        printf("*");
    printf("\n\n");
    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= 2 * n; ++j)
            if (j <= 2 * i)
                printf(" ");
        for (k = 0; k < n - i + 1; ++k)
            printf("*");
        if (1 == n - i + 1)
            continue;
        else
            printf("\n\n");
    }  */

    // 减少 j 循环次数的优化
    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= n; ++j)
            if (j <= n + 1 - i)
                printf("  ");  // 减少 j 循环次数的优化，打印两个空格
        for (k = 1; k <= i; ++k)
            printf("*");
        printf("\n\n");
    }
    for (i = 0; i <= n; ++i)
        printf("*");
    printf("\n\n");
    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= n; ++j)
            if (j <= i)
                printf("  ");  // 减少 j 循环次数的优化，打印两个空格
        for (k = 0; k < n - i + 1; ++k)
            printf("*");
        if (1 == n - i + 1)
            continue;
        else
            printf("\n\n");
    }
    printf("\n");
}

static void bit_choice1()
{
    unsigned char puc[4];
    struct tagPIM  // 位域结构，总大小为 2 字节
    {
        unsigned char ucPim1; // 占用 1 字节
        unsigned char ucData0 : 1;
        unsigned char ucData1 : 2;
        unsigned char ucData2 : 3; // ucData0、ucData1、ucData2 共占用 1 字节
    }*pstPimData;
    pstPimData = (struct tagPIM*)puc; // 指针类型转换
    memset(puc, 0, 4); // 全部清零，总 4 字节

    pstPimData->ucPim1 = 2;
    pstPimData->ucData0 = 3;
    pstPimData->ucData1 = 4;
    pstPimData->ucData2 = 5;
    printf("%02x %02x %02x %02x\n", puc[0], puc[1], puc[2], puc[3]);
    // 输出结果：0x02 0x29 0x00 0x00
}

static int* find_dogs(int* num, int len)
{ // 寻找“单身狗”的位置，最大时间复杂度为 O(2n + 32) 
  //核心原理：一个数与另一个数异或两次，得到该数本身，0 异或任何数都为该数本身
    int i, ret = 0;
    for (i = 0; i < len; ++i) // 过滤掉重复的数的结果，最大时间复杂度为 O(n)
        ret ^= num[i];//结果为 0 ^ dog1 ^ dog2 那么 ret 中至少有两位 1 也就是 dog1、dog2 不同的位
    for (i = 0; i < 32; ++i) // 找到 ret 的二进制原码第一位为 1 的位置，最大时间复杂度为 O(32)
        if (1 == ((ret >> i) & 1))
            break;   // 循环结束后，i 即为 ret 的第一位为 1 的位置
    // 异或两种分组，最大时间复杂度为 O(n)
    int j, dog1 = 0, dog2 = 0;
    for (j = 0; j < len; ++j)
        if (1 == ((num[j] >> i) & 1))
            dog1 ^= num[j];
    // ret 二进制中第一位为 1 的位置对应数组中该位置为 1 的数分一组并全部异或，
    // 这样结果就是第一个 “单身狗”
        else
            dog2 ^= num[j];
    // ret 二进制中第一位为 1 的位置对应数组中该位置不是 1 的数分一组并全部异或，
    // 第二个 “单身狗” 找到了
    int* two_dogs = (int*)malloc(2 * sizeof(int)); // 分配空间，最大时间复杂度为 O(1)
    if (NULL == two_dogs)
    {
        perror("malloc");
        return NULL;
    }
    else
    {
        two_dogs[0] = dog1;
        two_dogs[1] = dog2;
    }
    return two_dogs; // 返回第一个 “单身狗” 的地址，使用函数后续记得 free 喔
}

static int my_atoi(const char* str)
{  // 模仿 atoi 函数的实现
    if (NULL == str)
        return 0;
    int count = 0, sign = 1, ret = 0;
    /*while (' ' == *str || '\t' == *str || '\r' == *str || '\n' == *str || '\v' == *str
            || '\a' == *str || '\f' == *str || '\b' == *str) */
    while (isspace(*str))
        ++str; // 跳过空白字符
    if ('-' == *str)
    {
        sign = -1;
        ++str;
    }
    else if ('+' == *str)
        ++str;
    while ('0' <= *str && *str <= '9')
    {
        ret = ret * 10 + (*str - '0'); // 累加数字
        ++str;
        ++count;
    }
    if (count == 0) // 若没有数字，则返回 0
        return 0;
    else if (((ret >> 31) & 1) == 1 && sign == 1) // 若结果二进制最高位为 1，则溢出
        return 0x7fffffff; // 最大 32 位整数的正数
    else if (((ret >> 31) & 1) == 1 && sign == -1)
        return 0x80000000; // 返回最大 32 位整数的负数
    else
        return sign * ret;// 返回最终结果
}

static int swap_odd_even(int n)
{ // 交换整型值的二进制数的奇偶数位
    int mask = 0x55555555; // 奇数位掩码: 01010101 01010101 01010101 01010101
    int ret = 0;
    ret = ((n & mask) << 1) | ((n & ~mask) >> 1); // 交换奇数位和偶数位
    return ret;
}

static int fibonacci(int n)
{ // 计算斐波那契数列的第 n 个数
    //float phi = (1 + sqrt(5)) / 2; // 黄金比例数
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    int i = 0, pre1 = 1, pre2 = 0, ret = 0;
    for (i = 3; i <= n; ++i)
    {
        ret = pre1 + pre2;
        pre2 = pre1;
        pre1 = ret;
        //printf("%d ", ret);  // 打印斐波那契数列的前 n 个数
    }
    return ret;
}

static int min_steps_to_fib(int n)
{ // 计算某个数靠近斐波那契数列的最小步数
    if (n < 0)
        return -1;
    else if (n == 0 || n == 1 || n == 2 || n == 3)
        return n;
    /*int i = 1, f1, f2;
    while ((f2 = fibonacci(i)) < n)
        ++i;
    f1 = fibonacci(i - 1); // f1 < n <= f2
    if (n == f2)
        return 0; // 若 n 刚好等于斐波那契数列的第 i 个数，则步数为 0
    int step1 = 0, step2 = 0;
    while (n - step1 != f1)
        ++step1;
    while (n + step2 != f2)
    {
        ++step2;
        if (step2 > step1)
            return step1; // 提前结束
    }
    return step1 < step2 ? step1 : step2; // 可直接 return step2;  */

    // 优化版，利用斐波那契数列的过程，一步到位
    int i = 0, pre1 = 1, pre2 = 0, ret = 0;
    while (1)
    {
        if (n == ret)
            return 0; // 若 n 刚好等于斐波那契数列的第 i 个数，则步数为 0
        else if (n < ret)
        {
            int step1 = 0, step2 = 0;
            while (n - step1 != pre2)
                ++step1;
            while (n + step2 != pre1)  // 循环执行后，pre1 == ret
            {
                ++step2;
                if (step2 > step1)
                    return step1; // 提前结束
            }
            return step2;
        }
        ret = pre1 + pre2;
        pre2 = pre1;
        pre1 = ret;
        if (pre2 > n)
            return -1; // error返回 -1
    }
}

static char* replace_str(const char* str, const char* cold, const char* cnew)
{ // 实现字符串中字符 c 替换为 cs 的功能，返回替换后的字符串
    if (NULL == str || NULL == cold || NULL == cnew)
        return NULL;
    size_t sz = 1;
    size_t len_c = strlen(cold);
    size_t len_cs = strlen(cnew);
    char* p1 = (char*)str;
    while (*p1)
    {
        if (0 == strncmp(cold, p1, len_c))
        {
            sz += len_cs; // cs 的长度
            p1 += len_c - 1; // 跳过 c 的长度
        }
        else
            ++sz;
        ++p1;
    }
    char* new_str = (char*)malloc(sz + 1); // 申请空间，+1 用于 '\0'
    if (NULL == new_str)
    {
        perror("malloc");
        return NULL; // 内存分配失败，返回 NULL
    }
    char* p2 = new_str;
    while (*str)
    {
        if (0 == strncmp(cold, str, len_c))
        {
            strncpy(p2, cnew, len_cs);
            p2 += len_cs;
            str += len_c - 1; // 跳过 c 的长度
        }
        else
        {
            *p2 = *str;
            ++p2;
        }
        ++str;
    }
    *p2 = '\0'; // 字符串末尾添加 '\0'
    p2 = NULL; // 释放内存
    return new_str;
}


void test_work_one() {
    print_start_line("小作业一部分开始");
    // 打印向左指向的回旋镖箭头
    print_boomerang(5);

    // 位域选择题
    bit_choice1();

    // 在一个无序数组（除了两个“单身狗”数外，全是成对出现的数组）中，找出这两个数
    int arr1[10] = { 1, 2, 3, 4, 6, 1, 2, 3, 4, 7 };
    int* two_dog = find_dogs(arr1, 10); // 这里的 two_dog 是一个指针，指向堆区的动态内存地址
    printf("两个单身狗数为：%d 和 %d\n", *two_dog, *(two_dog + 1));
    free(two_dog);
    two_dog = NULL; // 防止野指针

    // atoi 函数的实现
    char str1[] = "-2147483649"; // 超出 int 范围（多 2 ）
    char str2[] = "1\n6sb'5";
    char str3[] = " \t\n\r\v +486.486\06sb'";
    printf("atoi(str1) 的值为：%d，atoi(str2) 的值为：%d，atoi(str3) 的值为：%d\n",
        atoi(str1), atoi(str2), atoi(str3));
    printf("my_atoi(str1) 的值为：%d，my_atoi(str2) 的值为：%d，my_atoi(str3) 的值为：%d\n",
        my_atoi(str1), my_atoi(str2), my_atoi(str3));

    // 交换一个整数的二进制数的奇数位与偶数位，即第一位与第二位交换，第二位与第三位交换，以此类推
#define swap_odd_even(num)  (((num) & 0xAAAAAAAA) >> 1) | ((num & 0x55555555) << 1)
        // 这里的位运算符 | 可换为 +
    int num1 = 0b1010101010, num2 = 486486486, num3 = 2147483647, num4 = 1073741824;
    printf("swap_odd_even(num1) = %d；swap_odd_even(num2) = %d\n",
        swap_odd_even(num1), swap_odd_even(num2));
    printf("swap_odd_even(num3) = %d, swap_odd_even(num4) = %d\n",
        swap_odd_even(num3), swap_odd_even(num4));

    // 判断一个正整数每次加一或减一，最少多少次才能等于斐波那契数组中的某个数
    printf("min_steps_to_fib(100) = %d\n", min_steps_to_fib(100));

    // 将字符串里面的空格符全部替换为 %20
    char str4[] = "hello world today is a good day";
    char* new_str4 = replace_str(str4, " ", "+++++");
    // 注意这里空格是字符串而不是字符，所以需要用双引号括起来，传字符（为整型）会报错
    printf("替换空格后的字符串：%s\n", new_str4);
    free(new_str4);
    new_str4 = NULL;
    print_end_line("小作业一部分结束");
}
